package com.jz;

import com.future.util.TreeNode;

import java.util.ArrayList;

/**
 * Description: JZ34 二叉树中和为某一值的路径(二)
 *
 * @author weiruibai.vendor
 * Date: 2022/9/5 12:09
 */
public class JZ34 {
    // {10,5,12,4,7},22
    public static void main(String[] args) {
        JZ34 jz34 = new JZ34();

        TreeNode head = new TreeNode(10);
        head.left = new TreeNode(5);
        head.right = new TreeNode(12);
        head.left.left = new TreeNode(4);
        head.left.right = new TreeNode(7);

        int target = 22;
        ArrayList<ArrayList<Integer>> arrayLists = jz34.FindPath(head, target);
        System.out.println();
    }

    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int expectNumber) {
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
        process(root, expectNumber, ans, new ArrayList<Integer>());
        return ans;
    }

    private void process(TreeNode head, int rest, ArrayList<ArrayList<Integer>> ans, ArrayList<Integer> tmpAns) {
        if (head == null) {
            return;
        }
        tmpAns.add(head.val);
        rest -= head.val;
        if (head.left == null && head.right == null && rest == 0) {
            ans.add(new ArrayList<Integer>(tmpAns));
        } else {
            process(head.left, rest, ans, tmpAns);
            process(head.right, rest, ans, tmpAns);
        }
        tmpAns.remove(tmpAns.size() - 1);
    }

}
